package listbyorder.access301_400.test322;

import java.util.Arrays;

public class Solution1 {

    // 超时
    private int res = Integer.MAX_VALUE;

    // 贪心算法的一种形式
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        dfs(coins, amount, 0, 0);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private void dfs(int[] coins, int amount, int s, int count) {
        if (amount < 0) return;
        if (amount == 0) {
            res = Math.min(count, res);
        }
        int temp = count;
        for (int i = s; i < coins.length; i++) {
            dfs(coins, amount - coins[i], i, temp + 1);
        }
    }

}
